package com.xk._01基础篇._00LeetCode._链表;

/*
 * 876. 链表的中间结点
 * https://leetcode.cn/problems/middle-of-the-linked-list/
 *
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 *
 * 1/2 = 0   [0]
 * 2/2 = 1   [0, 1]
 * 3/2 = 1   [0, 1, 2]
 * 4/2 = 2   [0, 1, 2, 3]
 * 5/2 = 2   [0, 1, 2, 3, 4]
 * 6/2 = 3   [0, 1, 2, 3, 4, 5]
 *
 */
public class Test06 {

    public ListNode middleNode(ListNode head) {
        if (head.next == null) return head;

        int count = 0;
        ListNode cur = head;
        ListNode mid = head;
        while (cur != null){
            count++;
            if (count % 2 == 0){
                mid = mid.next;
            }
            cur = cur.next;
        }

        return mid;
    }

    //快慢指针
    public ListNode middleNode1(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}
